（50分 多路归并 二分）技能升级

题目 技能升级

image-dd6f2faa

思路分析

每次加点提升最多的 用大根堆维护

拿到了一半的分 知足了 （前年py b组第8题）

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
priority_queue<PII> heap;
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        heap.push({a,b});
    }
    int res=0;
    while(m--){
        int addval=heap.top().first;
        int delval=heap.top().second;
        int nextaddval=heap.top().first-delval;

        heap.pop();

        res+=addval;
        heap.push({nextaddval,delval});
    }
    cout<<res;
    return 0;
}
image-f94fd5f1

我草 本来就是听听看 发现好像又悟到了什么 一开始以为什么是多路归并呢 慌得一批

我说听着这个思路怎么这么耳熟 原来之前已经接触过：蚯蚓

可以开多个优先队列 对头元素一定是这一路里最大的 那么只需要在多个对头中选一个最大的即可

本质是以空间换时间

看来又能整理出一类问题了 多路归并

但这道题……emm 暂时放一下 后面的二分没看懂怎么来的 分心了

代码实现

同类题型

视频讲解

⬅️ 鱼塘钓鱼 🏠 00-刷题理模型 ➡️ 6、特别数的和